HPAVC

home *** CD-ROM | disk | FTP | other *** search

/ HPAVC / HPAVC CD-ROM.iso / pc / CIS_GAME.ARJ / QMATH1.THD < prev next >

Wrap

Text File | 1993-06-25 | 63.2 KB | 1,498 lines

_____________________ Subj: Point-to-Point 2d Geometry _____________________ Fm: MIKE ROBEL 76446,1444 # 173935 To: Anyone Date: 01-Jun-92 22:25:39 I am working on a program, and I need a line to compute the bearing from my position to a target where I am at x,y and the target is at x1,y1. I tried using cotanget times the (x-x1)/(y-y1) but it only gives me a reading in 90 degrees, with a +/- depending on whether or not the position of the other object is left, right, up, or down. rembering my trig, that makes sense since i think tangents only go to 90 degrees, but is there any easy way to do this and get bearings from 0 to 360 degrees. Right now I am working this in quickbasic. Mike ........................................................................... Fm: hercules/Assoc. SysOp 75300,3472 # 173977 To: MIKE ROBEL 76446,1444 (X) Date: 02-Jun-92 00:39:19 Using your notation that you are at [x,y] and the target is at [x1,y1], the bearing to the target is arc-tangent [(y1-y)/(x1-x)], the result can be evaluated either in degrees or in radians. (It's ok to use arc-cotangent as in your example.) There are 4 cases to check: a) if (y1-y) and (x1-x) are both positive, then the bearing is between 0 to 90 degrees. b) if (y1-y) is positive but (x1-x) is negative, the the bearing is between 90 to 180 degrees. c) if (y1-y) is negative but (x1-x) is positive, then the bearing is between 180 to 270 degrees. d) if (y1-y) and (x1-x) are both negative, then the bearing is between 270 to 360 degrees. What this means is that you need to add a multiple of 90 degrees to the angle that you get from the arc-tangent. The value of the multiple is controlled by the outcome of the four conditions. There are probably better ways/algorithms to do this. I'm a lousy programmer. _____________________ Subj: Point-to-Line 2d Geometry _____________________ Fm: KGliner 70363,3672 # 320438 To: all Date: 25-Mar-93 18:27:32 Given a point at coordinates Px,Py, and a line segment with the endpoints X1,Y1 and X2,Y2, how does one find the closest distance between the point and the line segment? Kevin ........................................................................... Fm: Hans Peter Rushworth 100031,473 # 320619 To: KGliner 70363,3672 (X) Date: 25-Mar-93 21:50:17 I don't have a formula offhand, but I can tell you how to work it out with a little algebra on your part. The closest point will be either (X1,Y1) or (X2,Y2) or the point (Ix,Iy) in between that forms a right angle between the line from that point to (Px,Py), and the original line segment. Any point on the line bewteen points (X1,Y1) and (X2,Y2) can be expressed like this: Ix = X1 + a*(X2-X1) ---(1) Iy = Y1 + a*(Y2-Y1) ---(2) The value "a" is a paramter and will be between 0 and 1. If it is greater than or equal to 1 then the closest point is (X2,Y2). If it is less than or equal to zero, then the closest point is (X1,Y1). Thats the trivial solution. So how do you find "a"? Remember dot product of vectors? The dot product of two vectors is 0 if the angle between them is 90 degrees. The vectors in question are: [X2-X1,Y2-Y1] and [Px-Ix,Py-Iy]. The dot product of the vectors is (X2-X1)*(Px-Ix) + (Y2-Y1)*(Py-Iy) = 0. ---(3) That is not enough for a solution, since that is true for any point that lies on the line (PxIx,PyIy). You need to substitute the equations (1),(2) above for Ix and Iy (which are in terms of the parameter a) into equation (3). If you solve this you will get a value for a. Now see if a is in the range 0-1 and if so substitute it back into the equations (1) and (2), and this should give the result. Neat Huh? <g> Hope that helps (and is right!) Peter. ........................................................................... Fm: Hans Peter Rushworth 100031,473 # 320627 To: Hans Peter Rushworth 100031,473 (X) Date: 25-Mar-93 22:03:00 Again I misread the question ! Once you have the point Ix,Iy, it is a simple matter to work out the distance using the formula: distance = sqrt((Px-Ix)*(Px-Ix) + (Py-Iy)*(Py-Iy)) Substuting Ix & Iy with X1,Y1 or X2,Y2 if a is not in between 0 and 1. Peter. ........................................................................... Fm: Bob Provencher/GD SL 71621,2632 # 320949 To: KGliner 70363,3672 (X) Date: 26-Mar-93 13:45:38 Kevin - Let's see, if you can't project the point onto the line segment, then the shortest distance should be the min of the distance to the two end points. If you can project the point orthogonally onto the line, then the shortest distance should be the distance to the projection point. If Pete's method doesn't work out, I'll see if I can work this out. Bob ........................................................................... Fm: rod lentz 71163,57 # 338584 To: John Dlugosz [ViewPoint] 70007,4657 Date: 20-Apr-93 23:22:41 >> how the cos (atan ()) helps you find distance? Ok; pixture in 2d space the two points you want to find the distance of. Picture a right triangle connected to it, where the other 2 sides are parallel to the x & y axes, and the distance you're after is the hypotenuse. Given the ratio of the non-hypotenuse sides of a right triangle atan() returns the angle. The two "sides" you use are the separate distances in the x & y directions. Do some swapping of x & y, so that your value is always in the range 0..1, i.e. (minor axis / major axis). Index your table by (table size * minor axis / major axis). Now cos() of the angle from the atan() is the ratio of the length along the major axis to the length of the hypotenuse. Of course, making a table of cos(atan()) is the fastest way to go, rather than 2 separate tables. Hope that was clear enough ! - Rod ........................................................................... Fm: Vu Truong (Siliconis) 70242,3015 # 369363 To: Lary Myers 76004,1574 (X) Date: 05-Jun-93 01:00:35 I hope this equation helps (its from my calculus book!) | = Absolute Bar ^ = Raise to the Power of D= (|ax0+by0+C|)/(sqr(a^2+b^2)) Distance from point (x0,y0) to line (ax+by+c=0). ........................................................................... Fm: Bob Provencher/GD SL 71621,2632 # 369473 To: Lary Myers 76004,1574 (X) Date: 05-Jun-93 09:30:09 Hi Lary, If the point normal to the line (that the line segment is part of) intersects the line segment <whew> then the intersection to the line segment is the same as the intersection to the line. Otherwise, it would be the closest end-point. If that's not enough to go on, I'll work out the equations. Bob ______________________________ Subj: 3d to 2d ______________________________ Fm: KGliner 70363,3672 # 283627 To: all Date: 22-Jan-93 16:18:27 I've been doing some 3d work lately, and I've run into some problems projecting a point in 3d to a point in 2d. Normally this isn't difficult, but I'm having trouble accounting for the horizon. What I've got are the offset coordinates in 3d for the point relative to the center of the 'view'. I also know the distance to the horizon (ie. where it collapses to nothing). Without the horizon factored in, I could just take the x and y coordinates and use those as is. With the horizon, I need to scale them depending on the depth (the z coord). I tried using a linear scaling method (eg. if z is 1/2 the horizon, then reduce x and y by 50%). That produces values that are sometimes close (depending on the distance of the horizon), but incorrect. Anyways, my trig is rusty and I've completely forgotten calculus and all that matrix stuff. Any help on this would be much appreciated. ........................................................................... Fm: John Burkhard 71044,3263 # 283746 To: KGliner 70363,3672 (X) Date: 22-Jan-93 19:40:37 Scaling isn't all that complicated. You were kind of on the right track. If you have two points, call the first the eye point, and the second the focal point, you compute the distance from the eyepoint to the focal point, and use that in computing the 2d positions of your 3d points. Like: E = eye point F = focal point P = some arbitrary point |F| = distance between E and F (could be called the focal length) |P| = distance from E to P P.x = P.x * |F| / |P| P.y = P.y * |F| / |P| The closer you make F to E, the quicker things will shrink as they approach the horizon, and the farther away F is from E, the slower they shrink as they approach the horizon. For your application, you know the distance to the horizon, so you can select your |F| to be such that stuff becomes scaled too small for display at the desired distance away. ........................................................................... Fm: John Burkhard 71044,3263 # 285095 To: KGliner 70363,3672 (X) Date: 24-Jan-93 18:27:54 >> How do I remove the distortion when up close to objects in my field of view? (ie. if I have a string of points that constitute a straight line in 3d, I want to them to retain that straightness in 2d). << The method I presented is the same method used when ray tracing. Distortion is an inevitable artifact of this process. If you want to have a distortion free scaling, you could try the following: (this one's off the top of my head, so bear with me...) Single Point Perspective: Given H.z, the distance from the focal plane (z=0) to the horizon, the x and y components of an arbitrary point P will both be proportional to the distance from the horizon at which P lies. So: P'.x = P.x * ( H.z - P.z ) / H.z P'.y = P.y * ( H.z - P.z ) / H.z Where: 0 <= P.z <= H.z When P.z is 0, the point is on the focal plane, and will show at 100% scale. As P moves closer to H.z, it will be scaled linearly until P.z = H.z, at which time both the x and y components will map to 0. Two point and three point perspective are both a little more complex. I haven't worked out the math on them yet, but it should be an interesting exercise. ........................................................................... Fm: KGliner 70363,3672 # 287196 To: all Date: 28-Jan-93 02:57:38 Well, those 3d to 2d projection formulas seem to work pretty well. Now I'm stuck on what I think is a bug in the rotation-translation portion of my code. In a nutshell, I'm trying to translate the 3d global coordinates of a point to the 3d local coordinate system of the 'viewer'. I've been using a sort of hacked together arctangent table (using the slope of the line between the two points) and that works-- to a point (no pun intended). But I'm getting a slight distortion in my numbers so that when I connect a line between several points that were linear in the global coordinate system now appear just barely non-linear in the local coordinate system. I've been pouring over the Lee Adams books (High Performance CAD graphics in C and Visualization Graphics in C), but he's got so many variables without clear explanation it's been difficult for me to pick out the parts I'm looking for. I did notice that an arctangent call was unnecessary, and that I had to change my numbers slightly depending on what the angle was (ie. < 90, between 90 and 180, etc-- something I already do). But I got lost after that. Any suggestions? Thanks, Kevin ____________________________ Subj: more 3d to 2d ____________________________ Fm: KGliner 70363,3672 # 287699 To: John Burkhard 71044,3263 Date: 28-Jan-93 23:09:51 John (and Bob)- What I have is are the coordinates (Px,Py,Pz) of a point in a global 3d coordinate system. I also have the coordinates of the 'viewer', or camera, from which this point is being viewed (we'll call these coordinates Vx,Vy,Vz). In addition, I have the global XY, XZ, and YZ angles that the camera is oriented. What I want to be able to do is find the coordinates of the point P in the camera's local 3d coordinate system (where the camera sits at 0,0,0). The next step is to project it onto a 2d screen, but I've already got that part working (your earlier formula worked great for that). The overall goal here is to display a virtual 3d environment from any location and view within it (something I have already achieved, but not with the exact precision I want-- hence this question). Thanks, Kevin ........................................................................... Fm: Bob Provencher/GD SL 71621,2632 # 288055 To: KGliner 70363,3672 (X) Date: 29-Jan-93 18:36:26 Hi Kevin - If you want the co-ordinates of the point (Px,Py,Pz) relative to the viewer at (Vx,Vy,Vz) then it's (Px-Vx,Py-Vy,Pz-Vz) (call it Rx,Ry,Rz). Projecting the point onto the viewer screen can be done by scaling... Assuming +Z is into the screen, +Y is from the bottom to the top, and +X is from left to right (all co-ordinates are relative to the viewer), and Z1 is the distance from the viewer to the screen. The the X and Y coordinates of the point on the screen (relative to the center) are given by: X = Rx * Z1/Rz Y = Ry * Z1/Rz In the same units that X,Y,Z were originally in. I just came up with all this stuff off of the top of my head, so it may be completely wrong for all I know <g>. Bob ........................................................................... Fm: Bob Provencher/GD SL 71621,2632 # 289651 To: KGliner 70363,3672 (X) Date: 01-Feb-93 12:35:02 Hi Kevin - Sorry I couldn't remember the 2D matrix rotation stuff off the top of my head the other day. It's been a little while since I used it. I'm pulling this stuff straight out of one of my graphics book, in this case it's "Computer Graphics, A Programming Approach," by Steven Harrington, McGraw-Hill, 1987, ISBN 0-07-026753-7. The rotation transformation matrix, R, for rotation counterclockwise w degrees, about the point ( 0, 0 ) is: R = | cos w -sin w | | sin w cos w | To compute the co-ordinates of a point p = ( x, y ) after rotation, you do matrix multiplication on the point with R: p' = | x y | | cos w sin w | = | x cos w + y -sin w x sin w y cos w | | -sin w cos w | p' = ( x * cos(w) ) + ( y * -sin(w) ), ( x * sin(w) ) + ( y * cos(w) ) For example, rotating ( 1, 0 ) +90 degrees: p' = ( 1 * cos(90) ) + ( 0 * -sin(90) ), ( 1 * sin(90) ) + ( 0 * cos(90) ) p' = ( 0 ) + ( 0 ), ( 1 ) + ( 0 ) p' = 0, 1 rotating ( 1, 0 ) 45 degrees: p' = ( 1 * cos(45) ) + ( 0 * -sin(45) ), ( 1 * sin(45) ) + ( 0 * cos(45) ) p' = ( 0.707 ) + ( 0 ), ( 0.707 ) + ( 0.525 ) p' = 0.707, 0.707 rotating ( 0, 1.414 ) -45 degrees: p' = ( 0 ) + ( 1.414 * -sin(-45) ), ( 0 ) + ( 1.414 * cos(-45) ) p' = ( 0 ) + ( 1.414 * 0.707 ), ( 0 ) + ( 1.414 * 0.707 ) p' = 1, 1. If you use a lookup table, it seems to me that the equation for p' can be computed moderately fast. Hope this helps Bob ........................................................................... Fm: John Burkhard 71044,3263 # 289904 To: KGliner 70363,3672 (X) Date: 01-Feb-93 20:26:50 The mathematics for performing the translate and rotation in 3d are: Given: Q is the point to be translated and rotated; Q' is the result; T is the translation offset; r = roll angle; p = pitch angle; y = yaw angle; And R is the roll rotation matrix P is the pitch rotation matrix Y is the yaw rotation matrix Then: P' = R * P * Y * (Q-T) Where: Q, Q', T are of the form ( x, y, z ) And where: R = +- -+ | cos r -sin r 0 | | sin r cos r 0 | | 0 0 1 | +- -+ P = +- -+ | 1 0 0 | | 0 cos p -sin p | | 0 sin p cos p | +- -+ Y = +- -+ | cos y 0 -sin y | | 0 1 0 | | sin y 0 cos y | +- -+ The ROLL angle is the angle to rotate about the Z axis; The PITCH angle is the angle to rotate about the X axis; And the YAW angle is the angle to rotate about the Y axis. There are ways to write the above which eliminates floating point math entirely; only addition, subtraction, multiplication, division and square root. HTH, -jb ________________________ Subj: 3d Rotations _____________________________ ( see also the "Flights of Fantasy" thread(s) ) Fm: Mark Betz/GD SL 76605,2346 # 199351 To: Peter Rushworth 100112,1532 (X) Date: 12-Aug-92 23:10:18 We've run into a problem with the translation routines that handle moving the aircraft through 3 space. The method we're using starts out with an imaginary point x = 0, y = 0, z = distance travelled. This imaginary point assumes you have zero rotation relative to the world coordinate system, and are travelling along the z-axis (straight into the screen in our system). We then put the point through the following rotations, feeding the results of each into the next. The dX, dY, and dZ symbols refer to your actual rotation angles relative to the world axes, not the presumed 0 rotation angle implied by the imaginary starting point... Z rotation: X' = (X*COS(dZ)) - (Y*SIN(dZ)) Y' = (X*SIN(dZ)) + (Z*COS(dZ)) Z' = Z X rotation: X' = X Y' = (Y*COS(dX)) - (Z*SIN(dX)) Z' = (Y*SIN(dX)) + (Z*COS(dX)) Y rotation: X' = (Z*SIN(dY)) + (X*COS(dY)) Y' = Y Z' = (Z*COS(dY)) - (X*SIN(dY)) XPos += X'; YPos += Y'; ZPos += Z'; The last three statements translate your position back out to your starting point, and then add in the new deltas for the three axes. The problem is that we're getting the right values for change along each axis, but we're getting the wrong sign for various components, depending on the rotations. For example. going into this with the view rotated to look NE, if we feed in values which should cause the plane to move directly forward, we slide left along a line bisecting the wing, because X is getting smaller when it should be getting larger. So far the only way I can think of to correct the problem is to test the rotations going in, and apply some sign changes based on whatever rules I can discover. I can't help thinking that we're missing something, though, and that we shouldn't have to flip signs explicitly. Any ideas or suggestioins you might have would be greatly appreciated. If it's my turn to initiate the transatlantic phone call say the word <g>. --Mark __________________________ Subj: more 3d Rotations __________________________ Fm: Chris Lampton [GAMPUB] 76711,301 # 371227 To: All Date: 08-Jun-93 00:08:46 Okay, folks, I have a math question. It probably has a simple answer, but the question itself is rather difficult to express. Here's my best shot: I have an infinite plane defined in terms of two pieces of information: the normal of the plane and an arbitrary reference point somewhere on the plane. The normal is represented as a unit vector -- call it {nx,ny,nz} -- and the reference point as a set of x,y,z coordinates. (Call these rx,ry,rz.) I also know the x,y,z coordinates of a second point on the plane. (Call it px,py,pz) What I want to do is rotate the plane around the reference point into a new orientation, which would have a normal of {nx',ny',nz'}. (Specifically, I want to rotate it to {0,0,1}, which would make it parallel to the x,y plane.) The question is, how do I calculate the rotated coordinates (call them px',py',pz') of the point at px,py,pz, the second point on the plane? Seems like this should be easy to do, since the elements of the unit normal vectors appear to correspond to the sines and cosines of the rotations of the normal in the x,y, y,z and x,z planes. But I'm not quite sure how to get from one normal to another, i.e. how to figure the sine and cosine of the _difference_ between the two normals so I can use them to rotate the point from one to the other. The arccos and arcsin might come in handy -- I could use them to calculate the angles, then subtract the angles and perform the standard rotation operations on the point using the difference in the angles -- but I have a suspicion that there's a simpler way, since I already seem to _have_ the sines and cosines in the unit vectors. Should I subtract {nx,ny,nz} from {nx',ny',nz'} or vice versa? (This doesn't seem to work.) Take the dot product of the vectors? (This doesn't either.) Perform some other obscure vector operation? <g> Any suggestions? Clear as mud, right? But I'm sure somebody out there will understand what the heck I'm talking about. Hey, Pete...! --Chris ........................................................................... Fm: Hans Peter Rushworth 100031,473 # 372011 To: Chris Lampton [GAMPUB] 76711,301 (X) Date: 08-Jun-93 23:21:15 Chris, >> What I want to do is rotate the plane around the reference point into a new orientation, which would have a normal of {nx',ny',nz'}. This is a three step process Step 1: Translate the plane 1 so it's reference point is at the origin, Step 2: Rotate to align the normals Step 3: Translate back out to the reference point Now combine these three transformations (by matrix multiplication) to get a single transformation that does everything in one go. I'll assume steps 1 and 3 are no problem. Doing them allows you to do step 2 more easily. Onto step 2, finding a transform to align the normals... You could solve this using a standard transformation that rotates about an arbitrary axis a certain number of degrees. The axis would be defined by the cross product of the two normal vectors, and the angle is found using the dot product of the two normal vectors. The transform you can derive using quaternions. But I'll skip the working and just give you the result: c@ is cos of the angle, s@ is sine of the angle and a,b,c are the x,y,z components of the unit length cross product vector [ (a*a + c@*(1-a*a)) (a*b*(1-c@)-c*s@) (a*c*(1-c@) + b*s@) ] [ (a*b*(1-c@)) + c*s@) (b*b + c@*(1-b*b)) (b*c*(1-c@) - a*s@) ] [ (a*c*(1-c@)) - b*s@) (c*b*(1-c@)+a*s@) (c*c + c@*(1-c*c)) ] This may look complex, but actually there is a pattern and there are several simplifications, particularly cos(theta) and sin(theta) which can be found from: cos(@) = a.b (a,b here are unit length plane normals) sin(@) = axb/n (n is the unit length vector, normal to a and b) So no trig is needed! I have never had the need to use this transform, which is the result of considerable paper calculation using quaternions, so it's possible there is an error, and the above result differs in one sign from that published in F&VD (page 227 2nd Ed), which you should consult for more information. ........................................................................... Fm: Hans Peter Rushworth 100031,473 # 372040 To: Hans Peter Rushworth 100031,473 (X) Date: 09-Jun-93 00:21:15 I would add that there is probably a *much more direct* way of obtaining the rotation matrix transform of step 2, but that would require more thought and scribbling, and take longer to explain. Also I would caution you that a plane normal and one point only describe a plane, and not the points on the plane. The procedure I outlined does not take into consideration any rotation of the planes about the surface normal. it simply aligns the normals so the planes are parallel. You might have to perform an intermediate rotation step (step 2.5) to align the planes in some special way depending on the nature of the problem. ______________________ Subj: Union of >1 Rectangles _________________________ Fm: Lutz Kretzschmar 100023,2006 # 372221 To: all Date: 09-Jun-93 09:17:35 Hi all, I have a programming problem at the moment and think this is the right place to ask. I have a number of rectangles that may, or may not, overlap. I need to reduce this to a minimum number of non-overlapping rectangles. This is for a sort of a window manager. I keep track of what window regions need to be updated, and then blit from a virtual screen that contains the whole screen in its correct state to the actual display. Unfortunately, it's not feasable to just blit the whole thing over. So I'm looking for an algorithm that will minimize this time. Maybe a scanline-based edge intersection list would be a better algorithm, does anyone have experience with this? I was thinking that I could maintain a sorted list of edges per scanline, and eliminate or add edges as they appear during addition of new rects. Then blit scanline by scanline, using the edges in the list as boundaries. ........................................................................... Fm: Mark Betz/Ass't SysOp 76605,2346 # 372715 To: Lutz Kretzschmar 100023,2006 (X) Date: 09-Jun-93 22:07:57 Hi, Lutz. I'm not sure I understand the problem completely, but your message prompted a few thoughts. First, I'm not sure what you mean by "minimum number of non-overlapping rectangles". I'm assuming for the moment that you want to find the smallest rectangle which encompasses the area of the screen which needs to be redrawn. The ways to do this generally break down into two categories. The first is tracking the "damage rectangle" dynamically. In other words, as drawing operations take place on the screen you constantly compare all four corner coordinates of the affected rect against the current damage rectangle (start with a rectangle of 0 area in the center of the screen). Anytime that a coordinate falls outside the current range, the range is adjusted to encompass it. The second method involves calculating the damage rectangle at update time, by performing some comparisons against the rectangles affected by any drawing operations since the last update. A better way to handle windowing operations, imho, is to make the windows into proactive objects. There are again two general approaches. The first is to have each window store a copy of the background it obliterates, so that it can restore that background when it changes position. The downside of this is that it cannot know about changes to that background since the background was captured. A better way is exactly how MS Windows, and most other GUIs, do it, and that is to make each window responsible for repainting itself on command. --Mark __________________________ Subj: Pinball Formulas __________________________ Fm: Diana Gruber/Fastgraph 72000,1642 # 371480 To: Randy @ Safari 71165,3600 (X) Date: 08-Jun-93 12:42:06 Randy, I don't know *all* the equations by heart! I usually look them up in a college physics book. But here are some suggestions. The speed of the ball will be constantly changing according to the force applied. Change in speed is acceleration, Force comes from three sources: the springs, friction, and gravity. You can probably ignore friction because it will be trivial compared to the other two forces. The equation for acceleration is: a=f/m Since you don't know what the mass is, normalize it to 1. Then plug in values for f until the game 'feels' right. Velocity is calculated in units of pixels per clock tick. The equation is: v = v0 + at Position at any point in time is x = x0 + v[x]t + 1/2a[x]t^2 y = y0 + v[y]t + 1/2a[y]t^2 The angle you bounce off something is the same as the angle you hit it. I always thought a pinball machine would be real fun to write. If somebody writes a good one, let me know, I know a publisher who is looking for one. Diana __________________________ Subj: Fixed Point Math __________________________ Fm: KGliner 70363,3672 # 296776 To: all Date: 13-Feb-93 22:29:10 I've been going through my program code and replacing all my floating point code with 32-bit fixed point (where the upper 16 bits is the part to the left of the decimal, and the lower 16 bits is to the right), but I've run into a problem with some of the math. Addition and subtraction are no problem-- it's just certain circumstances of multiplication and division that I'm unsure about. For example, say I have two floating point numbers, x=1111.1111 and y= 2222.2222. If these were stored as 32 bit integers, then doing a calculation like x * y would create an overflow, and x div y would yield a result of zero. So the question is, how do I do this and still maintain the same (or close enough) precision to the floating point calculations (and in assembly language as well, since the whole reason for using integers is to optimize for speed)? ........................................................................... Fm: Hans Peter Rushworth 100031,473 # 297262 To: KGliner 70363,3672 Date: 14-Feb-93 20:47:24 Assuming you have a 386 or 486... Multiplication first: MOV EAX,x IMUL DWORD PTR y ; 64-bit result in EDX:EAX (32 bit fraction is in EAX) SHRD EAX,EDX,16 ; reposition binary pt, 32-bit result in EAX (16 bit fract) Division: MOV EAX,x ; These two lines load x into EDX:EAX CDQ ; SHLD EDX,EAX,16 ; convert 48.16-bit value to 32.32-bit one SHL EAX,16 ; SHLD does not effect the second operand (EAX) so repeat IDIV DWORD PTR y ; EAX = EDX:EAX/y (16.16-bit), EDX = EDX:EAX % y Note: these are *signed* multiplies/divides. precision is maintained. ........................................................................... Fm: Hans Peter Rushworth 100031,473 # 297700 To: KGliner 70363,3672 (X) Date: 15-Feb-93 15:22:30 Kevin, >> [Inline assembly kludge needed] Ok... You didn't hear it from me <g> but: CDQ: 66 99 SHRD EAX,EDX,16 : 66 0F AC D0 10 SHLD EDX,EAX,16 : 66 0F A4 C2 10 (all in hex) ........................................................................... Fm: KGliner 70363,3672 # 298005 To: Hans Peter Rushworth 100031,473 (X) Date: 16-Feb-93 01:16:13 Peter- Thanks, that sort of worked. That is, the divisor (in EAX) was correct, but the remainder (in EDX) wasn't. Perhaps it needs to be shifted 16 bits left? I'll experiment with it and see what happens, although part of the problem may just be my forcing it into inline. ........................................................................... Fm: Chris Lampton [GAMPUB] 76711,301 # 298520 To: KGliner 70363,3672 (X) Date: 16-Feb-93 23:25:44 After talking with you on the phone, I think I have a clearer idea where the problem is. For your purposes, you won't need the value in EDX after the division is performed. Everything you need will be in EAX, with exactly the 16.16 precision you want. Here's how it works in the code Peter gave you: When you start out, you have a 32-bit dividend with 16.16 precision, which we'll say looks like this in hex: 76543210 The first instruction of Peter's code: MOV EAX,x gets this value into EAX. Now we need to convert this number into a 64-bit value with 48.16 precision that spans the EAX (low 32 bits) and EDX (high 32 bits) register. We do this by sign-extending EAX into EDX with the CDQ (Convert Doubleword to Quadword) instruction: CDQ ; Now our number has become 0000000076543210 in EDX:EAX. Before we perform division, however, we have to add 16 bits more precision to the right of the decimal point, because we're going to lose those bits during division. We do this by shifting the digits of the 64-bit number in EDX:EAX 16 bits to the left. For reasons that are more easily understood if you consult a good 80386 programming manual, this requires _two_ shift instructions: SHLD EDX,EAX,16 ; convert 48.16-bit value to 32.32-bit one SHL EAX,16 ; SHLD does not effect the second operand (EAX) so repeat Now the number looks like this: 0000765432100000 Finally we perform the division: IDIV DWORD PTR y ; EAX = EDX:EAX/y (16.16-bit), EDX = EDX:EAX % y This divides the 64-bit number in EDX:EAX by the 32-bit fixed point number at y. Because this divisor also has 16.16 precision, the division has the effect of shifting the decimal point back 16 positions to the right in the quotient, which puts us back where we started -- with a 32-bit number in the EAX register that has 16.16 precision. Don't worry about what's in EDX, just use the number in EAX as your result. _______________________ Subj: Fixed Point Algorithms _______________________ Fm: Chris Lampton [GAMPUB] 76711,301 # 328647 To: Lutz Kretzschmar 100023,2006 (X) Date: 07-Apr-93 12:01:00 In principle, fixed-point math is quite simple. For speed, however, it's best done with 16:16 precision on an assembly language level, at least on a 32-bit chip. The reason for limiting the code to 16:16 is that, otherwise, you'll have to jump through hoops to keep from shifting bits off the end of a register (or integer variable) and into oblivion. Fixed point addition and subtraction are trivial; they work just like integer addition and subtraction. You just have to be sure that the decimal points are aligned in the two numbers to be added or subtracted. Multiplication and division are a bit trickier. Bear in mind that multiplication shifts your decimal point to the left and division shifts your decimal point to the right. Thus, you must combine the multiplication or division with a shift to make sure the decimal point ends up where you want it. (Despite the term "fixed point," the decimal point actually does a lot of floating around. You have to _work_ to keep it fixed.) With multiplication, you perform the shift after the operation. With division, you usually perform it _before_ the operation. The decimal points in the multiplier and multiplicand (or divisor and dividend) do not need to be aligned, but you do need to know where the decimal point is going to end up. Here's a simple rule: After multiplication, the number of digits following the decimal in the result will be the number of digits following the decimal in the multiplier PLUS the number of digits following the decimal in the multiplicand, like this: aaaaaaaaaaaa.aaaa x bbbbbbbbbbbb.bbbb -------------------- cccccccccccc.cccccccc Note that this is identical to the long multiplication procedure you learned in school, decimal placement and all. After division, the number of digits following the decimal in the result will be the number of digits following the decimal in the dividend MINUS the number of digits following the decimal in the divisor, like this: aaaaaaaaaaaa.aaaa % bbbbbbbbbbbbbb.bb ------------------- cccccccc.cc This is why you must shift to the right _before_ division, so that you don't lose any digits to the right of the decimal point. Here's a simple C demonstration of fixed point multiplication with 24:8 precision: long multiplier,multiplicand,product; product = multiplier * multiplicand >> 8; And here's a demonstration of fixed point division: long divisor,dividend,quotient; quotient = (dividend << 8) / divisor; Note that the leftmost eight digits of the result are lost in both cases. Thus, although the official precision of these fixed point variables is 24:8, the _effective_ precision is only 8:8 -- and we're using 32-bit _longs_ here! That's why fixed point is better performed in 80386 assembly language. The 386 32-bit multiplication instruction, while restricted to 32-bit operands, produces a 64-bit result. Thus, while the leftmost digits may be shifted out of the EAX register, they are preserved in the EDX register, from whence they can be shifted back into EAX. And the 386 also allows a 64-bit dividend in division instructions. Pete Rushworth posted some excellent code a while back for 386 fixed point. If he doesn't jump in here and post it again, I'll see if I can dig it out, assuming you're interested in working with 386 assembler. But bear in mind that these routines are still restricted to 16:16 precision. If you really need 32:32 precision, you've got a lot of work ahead of you, unless you're working on a 64-bit CPU! --Chris p.s. Sorry I can't point you toward any books, but I've never been able to find any that discuss it. I talk about this briefly in my book Flights of Fantasy, but I don't say anything I haven't told you in this message. ........................................................................... Fm: Chris Lampton [GAMPUB] 76711,301 # 328660 To: Lutz Kretzschmar 100023,2006 (X) Date: 07-Apr-93 12:22:42 Whoops, in that last message where I refer to shifting RIGHT before division, change that to shifting LEFT before division. I've always been a bit dyslexic.... <g> --Chris ........................................................................... Fm: KGliner 70363,3672 # 329382 To: Lutz Kretzschmar 100023,2006 Date: 08-Apr-93 18:25:32 Ok, this is straight from my code: Multiply a * b: Division: mov ebx,[a] mov eax,[dividend] mov eax,[b] mov ebx,[divisor] mul ebx xor edx,edx shr eax,16 div ebx shl edx,16 mov ecx,eax mov dx,ax mov eax,0ffffh mov [result],edx div ebx shr eax,16 sal ecx,16 mov cx,ax mov [result],ecx Both these work for positive numbers. You might be able to speed up the multiplication, and I know for sure that the division could be more efficient. For one thing, there should be a way to do it with only one div instruction, but I never could get it work that way. If you find a way to optimize it, let me know. Oh yeah, Randy (at Safari) helped me hack out the division routine, although he may not want credit for that<g>. I actually had quite a number of solutions when I posted a similar question about a month or two ago. This is the only one I could get to work though. Kevin ___________________________ Subj: Fractal Terrain ___________________________ Fm: Hans Peter Rushworth 100031,473 # 213126 To: Mark Betz/GD SL 76605,2346 (X) Date: 14-Sep-92 22:52:38 If you use a "plasma" type fractal for generating mountains, you can improve the "flatness" between the mountains and the sea by cubing the altitudes of the points and then dividing by a constant value. If the result is too "craggy" you can flatten the peaks using a square root (or similar) function in more or less the same way. The problem with this method is determining a realistic course for rivers, and man-made constructions like roads. There is also a rule (I think it's called Zipfs (sp?) law) that relates to the distribution of peak altitudes, that might be worth looking into. Peter. ........................................................................... Fm: Mark 'SAM' Baker 100025,444 # 213312 To: Mark Betz/GD SL 76605,2346 (X) Date: 15-Sep-92 14:01:49 Fractals are an excellent method of generating pseudo-random terrain. Plasma clouds are probably the easiest to use; but their are some algorithms in either 'The Beauty of Fractals' or 'The Mathematics of Fractals' that are specific to developing continental map simulacrums. For semi-realistic random-landscapes, fractals are excellent. ........................................................................... Fm: John Burkhard 71044,3263 # 281177 To: John W. Ratcliff 70253,3237 (X) Date: 18-Jan-93 17:00:33 Along the lines of fractals... Even with an FPU, computation times for generating the Mandlebrot set over the range -2,-2 .. 2,2 is *very* time consuming, especially at the resolution you're talking about. A couple of years ago, when I got hooked on fractals, a friend of mine suggested an interesting approach to plotting the set. Given that the points within the set are relatively uninteresting (and take the longest amount of time to compute), his approach concentrated on the points outside the set first, and then tackled the points within the set. He repeatedly subdivided the screen area into four equal sized windows, and calculated the Mandlebrot function for the center point in each sub region. If the point calculated was within the set, he added that region to a queue for later processing; otherwise, he recursively subsidived each of the sub regions, and so on until the region was 1 pixel big. Once the function backed all the way out, he grabbed the next region from the queue and continued. In pseudo code: add entire_screen_region to region_queue while region_queue is not empty process_region with head of region queue endwhile process_region:: if region is 1 pixel big computer mandlebrot value plot the appropriate color based upon result return to caller else subdivide region into 4 quadrants for each quadrant compute mandlebrot of center point if result is within the mandlebrot set add quadrant to region_queue return to caller else fill region with appropriate color, based upon result process_region with quadrant endif next endif At least I think that's pretty much how it went. One interesting side note about the above: While it does result in some extra computations, for the most part it's not that bad. And since the colored areas are filled in first, and since there's almost constant screen activity, it *appears* to be faster than the brute force method of scanning line by line. -jb ........................................................................... Fm: Chris Lampton [GAMPUB] 76711,301 # 330470 To: Ralph Wirthlin 76247,715 (X) Date: 10-Apr-93 12:12:14 I fiddled around with some code for generating fractal scenery objects while writing FLIGHTS OF FANTASY, but didn't include the code in the book because of technical problems involved in translating the fractal data to the data format I used for storing objects. (I do discuss it in theory, however, with a simple demonstration program.) Actually, there are probably an infinite number of ways to generate fractal landscapes, most of which I've never attempted (and probably haven't imagined). Most, however, are based on the same premise: Start with a simple shape and break it recursively into segments (breaking the segments into segments and so forth, until you've reached the desired recursive depth). Use a small (or not so small, depending how "rough" you want to the landscape to look) random factor to perturb, or "skew", each subsegment from the orientation of the main segment. For instance, a coastline (or river or highway) could start out as a straight line, be broken into two skewed segments (not _exactly_ in the middle), which would each in turn be broken recursively into two skewed segments, and so forth, until sufficient "crookedness" has been achieved. By using the same random number seed each time, the coastline can be made reproducible, so that it will always look the same when the viewer returns to it. This can be done either in real time (if your code is fast enough) or to generate static data that can be stored in the scenery database (if you have room for it). The method that I was tinkering with in FOF (but wound up not using) would have generated fractal mountains. The basic technique is this: Start out with a pyramid, i.e. a mountain made out of four triangles with a rectangular base. Break each triangle into four smaller triangles, like this: * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Note that this involves splitting each edge of the original triangle into two edges. This should be done with a random factor so that the break rarely occurs at the exact center of an edge and the break points should be randomly perturbed from the original line by a few units in the x and/or y directions to make the new edges slightly (or not-so-slightly) skewed. This gives the divided triangle a jagged, rocky look (which it does not have in my simple ASCII illustration). Then repeat this process recursively on all four smaller triangles, until you have as much detail as you need (or can handle). Do this with each triangular face of the original pyramid and you have a mountain. (One of the trickiest parts is making sure that all the mountain faces meet at common vertices.) Obviously you don't start drawing (or storing) any of this until you reach the lowest level of recursion; intermediate data should be discarded. I realize this is a somewhat simplistic explanation of fractal scenery generation, and probably doesn't begin to answer the questions that you have, but it establishes the principles. I plan to research this topic in greater detail (because I still have a lot of questions about it too). I'll let you know what I find. --Chris ........................................................................... Fm: Chris Lampton [GAMPUB] 76711,301 # 330906 To: Mitchell Waite 75146,3515 (X) Date: 10-Apr-93 22:51:28 As a matter of fact, there's been a lot of serious talk around here about how COMANCHE: MAXIMUM OVERKILL works. The present technique does _not_ seem to use fractals. I'm not really giving away any secrets (at least among this crowd) if I tell you that the NovaLogic programmers maintain a 2-dimensional integer array representing the terrain, where each element of the array represents the height of the corresponding piece of terrain above some fixed level. (Additional information, such as terrain color, may also be contained in the array elements.) They then apparently use a technique known as raycasting (a kind of highly simplified raytracing) to establish how these height fields would appear from the viewer's position. This is hard to explain, but...imagine that the viewport on the display is divided from left to right into vertical columns one pixel in width, each stretching from the top to the bottom of the viewport. (There would be 320 such columns in a full-screen mode 13h viewport.) A single ray (basically, a straight line) is "cast" from the viewer's position for each of these vertical columns. Each time the ray passes over a terrain element (which the COMANCHE developers apparently refer to as "voxels," though that's not how that term is traditionally used), a vertical segment of the current screen column representing the (rotated and perspective-projected) difference in height between that voxel and the previous voxel passed over by the ray is painted in the (light-sourced?) voxel color. Magically, this gives the appearance of a three-dimensional landscape. If you look closely at the COMANCHE screen, you'll see that it appears to be made out of vertically elongated pixels, which change their elongation as you move relative to the terrain. That's a pretty rough sketch of the technique, of course. It's a very clever -- and very fast -- method of drawing hyper-realistic terrain. The main problem at present is that the terrain array requires a lot of storage, limiting the terrain size and resolution. However, if someone found a way to combine it with fractal terrain generation techniques, it might be possible to generate nearly infinite amounts of high-resolution, stunningly-realistic terrain. I'm itching for a chance to experiment with these techniques and see if I can get them to work. And I'd love to write a book (or part of a book) about the results. I've played with the FRACTINT plasma fractals a bit, with some very interesting results. Wonder if there's a way to get _that_ sort_ of thing working in real time? It's a completely different technique than that used in COMANCHE, but probably more versatile and with more long-range possibilities. --Chris ........................................................................... Fm: John Dlugosz [ViewPoint] 70007,4657 # 330491 To: Ralph Wirthlin 76247,715 (X) Date: 10-Apr-93 12:28:01 Well, here is a simple example. It uses midpoint subdivision of triangles. void z (pair p, pair p1, pair p2, int n) { if (A[p.x][p.y] != 0) return; //already covered this one fpnum val= A[p1.x][p1.y] + A[p2.x][p2.y]; val += random (n); A[p.x][p.y]= val/2; // show what is happening plot (p); } /* /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\ */ void compute (pair p, int n) { const half_n= n/2; pair right= point (p.x+n, p.y); pair down= point (p.x, p.y+n); //find midpoints int midx= p.x+half_n; int midy= p.y+half_n; pair pr= point (midx, p.y); pair pd= point (p.x, midy); pair rd= point (midx, midy); // find z values z (pr, p,right, n); z (pd, p,down, n); z (rd, right,down, n); if (n != 1 && n != -1) { compute (p, half_n); compute (pr, half_n); compute (pd, half_n); compute (rd, -half_n); } } /* /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\ */ int main (int argc, char* argv[]) { if (argc > 1) seed= atol(argv[1]); setup_A(); activate (d); setup_d(); show_scale(); compute (point(0,0), 128); compute (point(128,128), -128); saveimage(); key::get(); return 0; } ________________________ Subj: Random Bit Generator ________________________ Fm: Serge Mathieu 71035,2771 # 250051 To: Mark Betz/Ass't SysOp 76605,2346 (X) Date: 23-Nov-92 22:22:45 Mark, I'm not sure if this is the right way to code it in asm... _PSEUDO-RANDOM SEQUENCE GENERATOR FOR 32-BIT CPUs_ by Bruce Schneier (DrDOBBS Journal) int RANDOM () { static unsigned long register; /*Register must be unsigned so right shift works properly.*/ /*Register should be initialized with some random value.*/ register = ((((register >> 31) /*Shift the 32nd bit to the first bit*/ ^ (register >> 6) /*XOR it with the seventh bit*/ ^ (register >> 4) /*XOR it with the fifth bit*/ ^ (register >> 2) /*XOR it with the third bit*/ ^ (register >> 1) /*XOR it with the second bit*/ ^ register) /*and XOR it with the first bit.*/ & 0x0000001) /*Strip all the other bits off and*/ <<31) /*move it back to the 32nd bit.*/ | (register >> 1); /*Or with the register shifted right.*/ return register & 0x00000001; /*Return the first bit.*/ } BASM (TP6 built-in asm, 286 code) (note:bits 1 to 32) for 2 x 16 bit registers: Seed in DX:AX cl contains number of bits to generate ch is random number (maximum 8 bits) bx used to xor bit 32 with bits 7,5,3,2,1 mov cl,number_of_bits_needed xor ch,ch @Bit_Loop: mov bh,dh {bit 32} mov bl,al {bits 7,5,3,2,1} shl bl,1 {bit 7 to upper bit} xor bh,bl {xor upper bits and don't care about others} shl bl,2 {bit 5} xor bh,bl shl bl,2 {bit 3} xor bh,bl shl bl,1 {bit 2} xor bh,bl shl bl,1 {bit 1} xor bh,bl shr dx,1 {shift seed 16 bits} rcr ax,1 {plus 16 bits for 32 bits} rcl ch,1 {ch builds random number from bit 1} and bh,10000000b {bit 8} or dh,bh {to update bit 32} dec cl jnz @Bit_Loop Serge Mathieu ........................................................................... Fm: Hans Peter Rushworth 100031,473 # 206819 To: Sarwan Narine 76675,164 (X) Date: 31-Aug-92 11:40:45 The most common and fast method is the "Linear Congruential Generator": X(n+1) = ((a*X(n))+c) mod m. where a,c,m are specially chosen constants. Knuth gives an in-depth analysis of this complex topic in "Seminumerical Algorithms". Another method that is useful for binary decision making purposes (ie random YES/NO decisions), is based on data scrambling and encryption schemes. These methods employ a shift register with the output data element being the exclusive or of selected bits in the register. The output data bit is fed back into the input of the register, and each clock produces a pseudo random bit. The choice of which bits to feedback and the initial value of the register is important in order to produce a long non-repeating sequence. Most Communications Theory textbooks describe this method when applied to Peter. ________________________ Subj: Point inside polygon? ________________________ Fm: Tim Koffley 70334,16 # 379820 To: all Date: 20-Jun-93 12:39:18 Ok geometry fans, anyone got a quick/easy algorithm for determining if a point is inside a *strictly convex* polygon? I'm translating a board game to Windows (via Visual Basic) and I'm trying to detect when the mouse moves over a "room" on the board. The rooms are n-vertex convex polygons. I'm looking for something quick (and possibly dirty) as the sucker is called anytime the mouse moves (and it *is* Basic). Thanks in advance, -tk ........................................................................... Fm: Patrick Reilly 71333,2764 # 380001 To: Tim Koffley 70334,16 (X) Date: 20-Jun-93 16:59:01 Tim, All I can think of is to walk through the line segments that make up the polygon and find all that intersect the x coord of the point and the y coord of the point; if you end up with at least 4, with at least one above, one below, one left and one right, its in the polygon. -Pat- ........................................................................... Fm: Tim Koffley 70334,16 # 380078 To: Patrick Reilly 71333,2764 (X) Date: 20-Jun-93 18:21:26 >All I can think of is to walk through the line segments that make up the polygon and find all >that intersect the x coord of the point and the y coord of the point; if you end up with at least >4, with at least one above, one below, one left and one right, its in the polygon. I kinda understand what you're saying. But... a) what about triangular rooms b) I'm not sure what you mean by "above, below, left, right" and how you determine a segment's "aboveness" or otherwise... If you feel like it, walk me through this case..... |\ | \ | \ o <----- the point in question | \ | \ ------------ If that works, show with the point inside. thanks, -tk ........................................................................... Fm: Patrick Reilly 71333,2764 # 380415 To: Tim Koffley 70334,16 Date: 21-Jun-93 01:16:47 Tim, For your triangle (or any other n-gon with vertices >= 3): |\ | \ | X o <----- the point in question | X | \ -------X---- The "X" indicates where a line segment from the triangle is intersected by the x, and y, coordinates of the point. It has 1 "X" to its left, and two "X"s below - the point is not contained within the triangle. |\ | X X o X <----- the point in question | \ | \ ---X-------- There is now an X in each direction from the point (one left, one right, one above and one below) - the point is contained in the triangle. |\ | \ X o <----- the point in question | \ | \ -----X------ The point IS one of the intersections - you have to decide whether it should be considered within or without the triangle. This will work with any convex 2D polygon. Algorithm: Let point = X,Y. Let N be the number of vertices in the polygon. Left left = top = right = bottom = False. For each vertex V in the polygon do Let VN be the next vertex from V (VN of V(N-1) is V(0)) <special case> If VN.x == V.x and VN.x == X then If (VN.y <= Y and V.y >= Y) or (VN.y >= Y and V.y <= Y) then <lies on a vertical line - immediately pass or fail> <special case> Else If VN.y == V.y and VN.y == Y then If (VN.x <= X and V.x >= X) or (VN.x >= X and V.x <= X) then <lies on a horizontal line - immediately pass or fail> <line is neither vertical nor horizontal> Else r = (X-V.x)*(VN.y-V.y)/(VN.x-V.x) + V.y If r < Y then Top = True; Else if r > Y then Bottom = True Else <pass/fail - point lies on the line> r = (Y-V.y)*(VN.x-V.x)/(VN.y-V.y) + V.x If r < X then Left = True Else If r > X then Right = True Else <pass/fail - point lies on the line> If Top = True and Bottom = True and Left = True and Right = True Pass. Else Fail. -Pat- ........................................................................... Fm: Chris Lampton [GAMPUB] 76711,301 # 380007 To: Tim Koffley 70334,16 (X) Date: 20-Jun-93 17:07:55 Here's a quote from Alan Watt's FUNDAMENTALS OF THREE-DIMENSIONAL computer graphics: "The sum of the angles between lines drawn from the point to each vertex is 360 degrees if the point is inside the polygon, but not if the point lies outside." That sounds like a lot of work to put yourself and your program through, especially if the code is to be executed every time the mouse moves. The quickest and dirtiest alternative I can think of would trade off a big chunk of memory for speed: Set aside a byte array (or the closest VB equivalent) in which each element corresponds to a pixel location on the game board and contains the number of the room of which that pixel is part (or a value indicating that it's not part of a room). For the cost of an array index, you can know whether the mouse is inside a room and which room it is inside. --Chris ........................................................................... Fm: Tim Koffley 70334,16 # 380079 To: Chris Lampton [GAMPUB] 76711,301 (X) Date: 20-Jun-93 18:21:32 >graphics: "The sum of the angles between lines drawn from the point to each vertex is 360 >degrees if the point is inside the polygon, but not if the point lies outside." Thanks for the info. Of course, I *knew* about that property of a convex polygon, I just...er....FORGOT OK? <g>. That might not be *too* bad cuz most rooms are either 4 or 5 vertices and I've split the board into four regions to narrow/speed the search a bit. *Plus* I now realize I can discount positions of a certain color (talk about digging!). >can think of would trade off a big chunk of memory for speed: Set aside a byte array in which >each element corresponds to a pixel location on the game board Your alternate idea is fine BUT, I'm trying to keep with Windows' silly measurement system of "twips" for other practical reasons and, besides, my board bit map is roughly 1000x800 pixels! -tk ........................................................................... Fm: Chris Lampton [GAMPUB] 76711,301 # 380099 To: Tim Koffley 70334,16 (X) Date: 20-Jun-93 19:02:28 >my board bit map is roughly 1000x800 pixels! Hey, that would only be a 782 kilobyte array! Cheap at the price! <g> Heck, if you can use pixel color to trivially dismiss positions -- use it! The ideal would be to use a different interior palette for every polygon, so that the board bitmap itself could be used to easily differentiate polygons. Of course, that's a bit of a kludge, but I'm always on the lookout for a useful kludge. ;-) --Chris ........................................................................... Fm: Jez San @ Argonaut 72247,3661 # 380148 To: Tim Koffley 70334,16 (X) Date: 20-Jun-93 19:48:40 tk - use a bounding rectangle that totally contains your polygon to do trivial checking to see which area of the screen the mouse pointer is in, ie: to within 1 or 2 possible polygons. Then you can do a simple plane equation check for each edge of the polygon to ensure that the point of the mouse pointer is on the correct side of each plane (ie: checking that the normal to the plane always points away from the point, or something similar). -- Jez. ........................................................................... Fm: David Laturner 100031,1127 # 380461 To: Tim Koffley 70334,16 Date: 21-Jun-93 06:03:45 How about a sparse array? For each pixel row in the game board, store the columns where rooms start and end ( or vice versa ). Then your check will be a simple linear search along the row the mouse is in. Dave. ........................................................................... Fm: Tim Koffley 70334,16 # 381110 To: Patrick Reilly 71333,2764 (X) Date: 21-Jun-93 22:32:01 Thank a lot for the reply. I now understand what you're talking about. I'm currently trying the "Total interior angles from the point = 360" method. It's ok for now but I might have to try something different later. Thanks again! -tk ........................................................................... Fm: Tim Koffley 70334,16 # 381117 To: David Laturner 100031,1127 (X) Date: 21-Jun-93 22:33:38 >For each pixel row in the game board, store the columns where rooms start and end ( or vice >versa ). Then your check will be a simple linear search along the row the mouse is in. Another fine idea! Thanks... -tk ...........................................................................